/**
 * https://leetcode.cn/problems/count-special-integers/submissions/572324440/
 * 2376. 统计特殊整数
 * difficulty 陈贝纯 2024.10.13
 * 数位dp
 */

class Solution {
public:
    bool visit[10];
    int l=-1;
    int t;
    int sum=9;
    void dfs(int num,int n){
        if(n>=l){
            if(num<=t)
            sum++;
            return;
        }for(int i=0;i<10;++i){
            if(!visit[i]){
                visit[i]=true;
                dfs(num*10+i,n+1);
                visit[i]=false;
            }
        }
    }
    int countSpecialNumbers(int n) {
        int j=n;
        t=n;
        if(n<10)
        return n;
        while(j/10){
            l++;
            j/=10;
        }
        int d=9;
        int num=9;
        cout<<l<<endl;
        for(int i=0;i<l;++i){
            num*=d;
            sum+=num;
            d--;
        }
        sum+=((j-1)*(num/9*d));
        cout<<sum<<endl;
        l++;
        if(l==9&&j==2)
        return sum;
        visit[j]=true;
        dfs(j,0);
        return sum;
    }
};